import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-22
 * Time: 22:33
 */
/*
*  时间复杂度：O（n*log n)
* 空间复杂度：O（1）
* 稳定性：不稳定
* */
public class HeapSort {
     //向上调整为大根堆
    public static  void shiftDown(int []arr,int parent,int len){
        int child=parent*2+1;
        while(child<len){//保证有左孩子
            //比较左右孩子的最大值
            if(child+1<len && arr[child]<arr[child+1]){//如果有右孩子
                child++;
            }
            if(arr[child]>arr[parent]){
                int tmp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=tmp;
            }else{
                break;
            }
        }
    }

    //建堆
    public static void createBigheap(int []arr){
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            shiftDown(arr,i, arr.length);//arr.length跟len对应
        }
    }

    //堆排，交换和调整
    public static void heapSort(int[] arr){
        createBigheap(arr);
        int end= arr.length-1;//记录每次排完序的最后一个元素
        //交换0下标元素和最后一个元素
        //为什么是交换0下标和最后一个下标元素来排序，因为是一个大根堆，当执行到最后只剩0下标和左右子树两个时，那么下面的已经全部有序，此时0下标子树还是大根堆，所以需要把父亲节点和孩子节点的元素互换
        while(end>0) {//当end<=0时就不换了
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            shiftDown(arr, 0, end);//向上调整0下标子树
            end--;
        }
    }

    public static void main(String[] args) {
        int []arr={13,23,2,7,67,22};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
